package pers.whj.util.list;

public class MaxHeap<T> extends SeqList<T> implements Heap<T> {
    public MaxHeap() {
        super();
    }

    public MaxHeap(int initLength) {
        super(initLength);
    }

    public MaxHeap(T[] data) {
        super();
        if (data != null) {
            insert(0, data);
            adjust();
        }
    }

    @Override
    public void adjust() {
        if (mLength > 1) {
            int i = (mLength - 2) / 2;
            while (i >= 0) {
                siftDown(i, mLength - 1);
                i--;
            }
        }
    }

    @Override
    public boolean insert(T data) {
        if (super.insert(data)) {
            siftUp(mLength - 1);
            return true;
        }
        return false;
    }

    @Override
    public boolean insert(T[] data) {
        if (data == null) {
            return false;
        }
        if (mLength + data.length > getMaxLength() && !canResize()) {
            return false;
        }
        for (T tmp : data) {
            super.insert(tmp);
            siftUp(mLength - 1);
        }
        return true;
    }

    @Override
    public T delete() {
        T data = data(0);
        mData[0] = mData[mLength - 1];
        super.delete();
        if (mLength > 1) {
            siftDown(0, mLength - 1);
        }
        return data;
    }

    @Override
    public T peek() {
        return data(0);
    }

    @SuppressWarnings({"unchecked"})
    private void siftDown(int start, int end) {
        // assert that start and end are valid
        int j = start * 2 + 1;
        Comparable<T> tmp = (Comparable<T>) mData[start];
        while (j <= end) {
            if (j < end && ((Comparable<T>) mData[j]).compareTo(data(j + 1)) < 0) {
                j++;
            }
            if (tmp.compareTo(data(j)) >= 0) {
                break;
            } else {
                mData[start] = mData[j];
                start = j;
                j = j * 2 + 1;
            }
        }
        mData[start] = tmp;
    }

    @SuppressWarnings({"unchecked"})
    private void siftUp(int start) {
        // assert that start is valid
        int i = (start - 1) / 2;
        Comparable<T> tmp = (Comparable<T>) mData[start];
        while (start > 0) {
            if (tmp.compareTo(data(i)) <= 0) {
                break;
            } else {
                mData[start] = mData[i];
                start = i;
                i = (i - 1) / 2;
            }
        }
        mData[start] = tmp;
    }
}